Interactive computer generated displays provide for the visualization of realistic looking, three-dimensional models. Such models, under user control, are useful for both design evaluation and training and virtual environments, as may be found, for example, in mechanical computerized design systems. Such computer visualization systems provide images of a three-dimensional, complex structure on the screen of a computer workstation as seen from a simulated observer's viewpoint under interactive control by the user. If the computer generated display can be rendered smoothly and quickly enough, the user is provided an illusion of real-time exploration of a virtual environment under simulated observer movement through the structure.
A particular application for an interactive, computer generated visualization system of a complex structure is found in the modeling of highly complex structure, such as aircraft. A system which allows the user interactive movement throughout the structure can aid in numerous aspects related to the ultimate success of the product. For example, an interactive display of a complex aircraft structure can identify interference and fit problems, provide the ability to "see" areas of the product normally hidden in a physical mock-up, design routing of ducts and wiring through crowded areas, facilitate the work of integrated product teams by providing a "live" model and reduce cycle time and cost of the production of illustrations and training media. As computer graphic based systems have matured, so have the three-dimensional model databases that its methods were meant to display. Because real-world structure contains far more complexity than can be reasonably stored on computer storage media, the complexity of models developed has traditionally exceeded the capacity of the hardware required to display it. To deal with this problem, various methods have been developed to reduce the complexity of models while attempting to effect only minor changes on the perceived complexity to the eye. These methods may be divided into two categories: culling and detail elision.
Culling is the practice of not displaying objects that are invisible from a current viewing position. Such objects are considered "culled" from the scene. Objects may be culled either from being hidden by another object or being outside the current viewing frustum. While culling to the viewing frustum is often straightforward, culling occluded objects can be difficult, although algorithms have been devised to solve this problem. The key to culling is having a fast method of determining the visibility of all objects in a scene.
Detail elision is the practice of displaying an object at a varying level of detail depending on the object's importance to the perceived complexity of the scene. This perceived importance has traditionally been measured by the size of the object in the screen picture elements (pixels). The key to using detail elision is to have several levels of detail available for all complex objects in the scene.
Although both of the techniques described above increase the speed of the image rendering process, neither process efficiently renders complex models containing millions of polygons at acceptable, real-time frame rates, such as 15-30 frames per second. For example, culling does not perform fast enough to keep pace with drawing a scene every 30th of a second. Detail elision, on the other hand, is most useful in capturing the complexity of patterns or textures in objects, especially two-dimensional structures or features. However, textures and patterns are far less useful in engineering visualizations, because objects look different from different viewpoints, while a texture correctly captures an object's appearance from only one viewpoint.
What is needed is a method and apparatus that is capable of processing a vast amount of objects at a speed fast enough to keep pace with drawing a scene at a real-time frequency. The method and apparatus should refrain from processing objects that fall outside of the display's boundaries or that are completely occluded by another object. However, processing of the objects should be decoupled from drawing the appropriate objects so the speed at which the objects are drawn is not slowed to the speed at which the objects are being processed. As described in the following, the present invention provides a method and apparatus that meet these criteria and solves other shortcomings in the prior art.